package com.jack.leetcode.每日一题;

import java.util.Arrays;

/***
 * @author zhangjie
 * @date 2020/4/11 21:56
 */
public class 鸡蛋掉落 {

    public static void main(String[] args) {
        int k = 2,N=6;
        System.out.println(superEggDrop(k,N));
        System.out.println("second"+secondFun(k,N));
        k=3;
        N=6;
        System.out.println(superEggDrop(k,N));
        System.out.println("second"+secondFun(k,N));
        k=3;
        N=14;
        System.out.println(superEggDrop(k,N));
        System.out.println("second"+secondFun(k,N));
        k=1;
        N=14;
        System.out.println(superEggDrop(k,N));
        System.out.println("second"+secondFun(k,N));
    }

    public static int superEggDrop(int K, int N) {
        if(K == 1){
            return N;
        }
        int toBinary = K-1;
        int badest = 0;
        for(int i=0;i<toBinary;i++){
            badest++;
            badest = (badest+1+N)/2;
        }
        return toBinary+(N-badest);
    }

    public static int secondFun(int K,int N){
        int[][] dp = new int[N+1][K+1];

        for(int i=0;i<=N;i++){
            Arrays.fill(dp[i],i);
        }
        for(int i=0;i<=K;i++){
            dp[0][i] = 0;
        }
        dp[1][0] = 0;
        for(int i=1;i<=K;i++){
            dp[1][i] = 1;
        }
        for(int i=0;i<=N;i++){
            dp[i][0] = 0;
            dp[i][1] = i;
        }
        for(int i=2;i<=N;i++){
            for(int j=2;j<=K;j++){
                int left = 1;
                int right = i;
                while(left < right){
                    int mid = (left +right+1)/2;
                    int breakCount = dp[mid-1][j-1];
                    int notBreakCount = dp[i-mid][j];
                    if(breakCount>notBreakCount){
                        right = mid-1;
                    }else{
                        left = mid;
                    }
                }
                dp[i][j] = Math.max(dp[left-1][j-1],dp[i-left][j])+1;
            }
        }
        return dp[N][K];
    }
}
